home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / TEMP / GNU / bison / Recursion < prev    next >
Text File  |  1995-06-28  |  2KB  |  64 lines
  1. Recursion
  2. Previous: <Rules=>Rules> * Next: <Semantics=>Semantics> * Up: <Grammar File=>GrammarFil>
  3.  
  4. #Wrap on
  5. {fH3}Recursive Rules{f}
  6.  
  7. A rule is called {fUnderline}recursive{f} when its {fStrong}result{f} nonterminal appears
  8. also on its right hand side.  Nearly all Bison grammars need to use
  9. recursion, because that is the only way to define a sequence of any number
  10. of somethings.  Consider this recursive definition of a comma-separated
  11. sequence of one or more expressions:
  12.  
  13. #Wrap off
  14. #fCode
  15. expseq1:  exp
  16.         | expseq1 ',' exp
  17.         ;
  18. #f
  19. #Wrap on
  20.  
  21. Since the recursive use of {fCode}expseq1{f} is the leftmost symbol in the
  22. right hand side, we call this {fUnderline}left recursion{f}.  By contrast, here
  23. the same construct is defined using {fUnderline}right recursion{f}:
  24.  
  25. #Wrap off
  26. #fCode
  27. expseq1:  exp
  28.         | exp ',' expseq1
  29.         ;
  30. #f
  31. #Wrap on
  32.  
  33. Any kind of sequence can be defined using either left recursion or
  34. right recursion, but you should always use left recursion, because it
  35. can parse a sequence of any number of elements with bounded stack
  36. space.  Right recursion uses up space on the Bison stack in proportion
  37. to the number of elements in the sequence, because all the elements
  38. must be shifted onto the stack before the rule can be applied even
  39. once.  \*Note <Algorithm=>Algorithm>: The Bison Parser Algorithm , for
  40. further explanation of this.
  41.  
  42. {fUnderline}Indirect{f} or {fUnderline}mutual{f} recursion occurs when the result of the
  43. rule does not appear directly on its right hand side, but does appear
  44. in rules for other nonterminals which do appear on its right hand
  45. side.  
  46.  
  47. For example:
  48.  
  49. #Wrap off
  50. #fCode
  51. expr:     primary
  52.         | primary '+' primary
  53.         ;
  54.  
  55. primary:  constant
  56.         | '(' expr ')'
  57.         ;
  58. #f
  59. #Wrap on
  60.  
  61. defines two mutually-recursive nonterminals, since each refers to the
  62. other.
  63.  
  64.